package a.codetop;

import org.junit.Test;
import 其他.DataStructure.TreeNode;

public class _14二叉树最近公共祖先 {
    @Test
    public void test() {
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        t1.left=t2;t1.right=t3;

        System.out.println(lowestCommonAncestor(t1,t2,t3));
    }

    TreeNode res,p,q;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        this.p=p;this.q=q;

        back(root);
        return res;
    }

    private int back(TreeNode cur) {
        if(cur.left==null && cur.right==null){
            if(cur==p||cur==q) return 1;
            return 0;
        }

        int L=0,R=0;
        if(cur.left!=null) L=back(cur.left);
        if(cur.right!=null) R=back(cur.right);

        //pq在不同子树
        if(L+R==2){
            res=cur;
            return 1234;//无所谓的数字了
        }
        //pq其中一个是头节点，同树
        else if(L+R==1 && (cur==p||cur==q)){
            res=cur;
            return 1234;
        }
        //其他: 二叉树后序包含本身：curRes=cur+L+R
        else {
            return (cur==p||cur==q)?1:0 + L+R;
        }
    }

}
